#include<iostream>
#define MAX_SIZE 110
using namespace std;

typedef struct {
	int SqBiTNode[MAX_SIZE];
	int ElemNum;
}Tree;


bool isSearchTree(Tree root) {
	int i = 0; 
	while (2 * i + 1 < root.ElemNum) {
		if (root.SqBiTNode[i] == -1) i++;	//空节点
		else if (root.SqBiTNode[2 * i + 1] == -1 && root.SqBiTNode[2 * i + 2] != -1) {	//左子树为空
			if (root.SqBiTNode[i] > root.SqBiTNode[2 * i + 2])
				return false;	//根节点大于右子树
		}
		else if (root.SqBiTNode[2 * i + 1] != -1 && root.SqBiTNode[2 * i + 2] == -1){	//右子树为空 
			if (root.SqBiTNode[i] < root.SqBiTNode[2 * i + 1])
				return false;	//根节点小于左子树
		}
		else if (root.SqBiTNode[2 * i + 1] == -1 && root.SqBiTNode[2 * i + 2] == -1) {	//左右子树都为空
			break;
		}
		else {	//左右子树都不为空
			if (root.SqBiTNode[i] < root.SqBiTNode[2 * i + 1] || root.SqBiTNode[i] > root.SqBiTNode[2 * i + 2])
				return false;	//根节点小于左子树或者大于右子树
		}
		i++;
	}
	return true;
}

bool JudgeBST(Tree t, int i, int *val) {
	if (t.SqBiTNode[i] == -1 || i >= t.ElemNum)
		return true;
	//左树
	if (!JudgeBST(t, 2 * i + 1, val))
		return false;

	if (t.SqBiTNode[i] <= *val)
		return false;
	*val = t.SqBiTNode[i];

	//右树
	if (!JudgeBST(t, 2 * i + 2, val))
		return false;
}

void main() {
	Tree t1;
	t1.ElemNum = 10;
	t1.SqBiTNode[0] = 40;
	t1.SqBiTNode[1] = 25;
	t1.SqBiTNode[2] = 60;
	t1.SqBiTNode[3] = -1;
	t1.SqBiTNode[4] = 30;
	t1.SqBiTNode[5] = -1;
	t1.SqBiTNode[6] = 80;
	t1.SqBiTNode[7] = -1;
	t1.SqBiTNode[8] = -1;
	t1.SqBiTNode[9] = 27;

	Tree t2;
	t2.ElemNum = 11;
	t2.SqBiTNode[0] = 40;
	t2.SqBiTNode[1] = 50;
	t2.SqBiTNode[2] = 60;
	t2.SqBiTNode[3] = -1;
	t2.SqBiTNode[4] = 30;
	t2.SqBiTNode[5] = -1;
	t2.SqBiTNode[6] = -1;
	t2.SqBiTNode[7] = -1;
	t2.SqBiTNode[8] = -1;
	t2.SqBiTNode[9] = -1;
	t2.SqBiTNode[10] = 35;

	bool flag;

	flag = isSearchTree(t1);
	cout << "t1:" << flag << endl;

	flag = isSearchTree(t2);
	cout << "t2:" << flag << endl;



	int val = INT_MIN;
	flag = JudgeBST(t1, 0, &val);
	cout << "t1:" << flag << endl;

	val = INT_MIN;
	flag = JudgeBST(t2, 0, &val);
	cout << "t2:" << flag << endl;

}